#include <stdio.h>
#include "qsortA.h"
#include <assert.h>
#include <pthread.h>
#include <stdlib.h>
#include <time.h>

/* Quicksort: A means with which to sort an array of positive integers.
 * Currently working, or so I believe anyway. Sorts lists of integers extremely
 * fast. Currently supports up to 100 spawnable threads, though this can be changed in
 * the code below.
 * Due to GCC/G++ having some retarded code compiling preferences, you need
 * special flags to compile this.
 * 
 * [pwnsauce@SkyNet]$ g++ -lpthread -fpermissive -o qsort qsortA.c
 * 
 * Will compile the code, but give you bunch of warning messages. Not sure how
 * to hide those yet, but I am sure there is a flag for it.
 *
 * Todo:
 * 1) Find and fix the memory leak for the code -- DONE 
 *    Note that the 56 bytes still reachable is created by the pthread_exit(),
 *    not a bug. 
 * 2) Find the correct flag to remove g++ warnings on compile
 * 3) Fix ugly code -- Semi done
 * 4) Add commandline options (argc/argv)
 * 5) Add dynamicly adjusted array size for threading - possibly unnecessary.
 *    As a command line tool, it is rare that one will need to sort more than
 *    460 elements. Needs more looking into yet anyway.
 *
 * Brad Glasbergen
 */

//GLOBAL VARIABLES, FOR USE WITH PTHREADS

//Change the line below to adjust number of spawnable threads
pthread_t thread_id[900000]; 
pthread_mutex_t mutex1 = PTHREAD_MUTEX_INITIALIZER;
int counter = 1;

//The Arguments Structure to allow for the passing of multiple variables

struct args {
        int **a;
        int left;
        int right;
};

/*QSORT: 
 * This is the function that does all of the threading for the program
 * Makes use of Mutex variables and thread joining to control the output and
 * ensure code correctness.
 * Overall the code is efficient, but kind of ugly due to the requirements for
 * POSIX threading.
 */

void *qsort(void* argss){
        struct args *args = malloc(sizeof(struct args));
        args->a = ((struct args*) argss)->a;
        args->left = ((struct args*) argss)->left;
        args->right = ((struct args*) argss)->right;
        if(args->left < args->right){
                int mid = partition(*(args->a), args->left, args->right);
                int temp = 0;
                struct args *args1 = malloc(sizeof(struct args));
                struct args *args2 = malloc(sizeof(struct args));
                args1->a = args->a;
                args2->a = args->a;
                args1->left = args->left;
                args2->left = mid+1;
                args1->right = mid-1;
                args2->right = args->right;
                pthread_mutex_lock(&mutex1);
               temp=counter;
                counter = counter + 2;
                if(counter > 90000){
                        abort();
                }
                pthread_mutex_unlock(&mutex1);
                pthread_create(&thread_id[temp],NULL,qsort,(void *) args1);
                pthread_join(thread_id[temp],NULL);
                pthread_create(&thread_id[temp+1],NULL,qsort,(void *) args2);
                pthread_join(thread_id[temp],NULL);
                free(args1);
                free(args2);
        }
        free(args);
        pthread_exit(NULL);
}

//The quicksort function - this serves as a helper function to qsort

void quicksort(int a[], int n){
        struct args *args1 = malloc(sizeof(struct args));
        args1->a = &a;
        args1->left = 0;
        args1->right = n-1;
        pthread_create(&thread_id[0],NULL,qsort,(void *)args1);
        pthread_join(thread_id[0],NULL);
        free(args1);
}

void print_array(int a[], int n){
        printf("[ ");
        for(int i = 0; i < n; i++){
                printf("%d ", a[i]);
        }
        printf("]\n");
}

//The heart of the program - partition. 

int partition(int a[], int left, int right){

        //Handles the 2 element lists, which were causing issues, the negative 
        //1 will stop this recursive call of the program b/c qsort will terminate in the next recursion.

        if(right-left == 1){
                if(a[left] > a[right]){
                        int temp2 = a[right];
                        a[right]=a[left];
                        a[left]=temp2;
                        return -1;
                }
        }

        int fe = a[left];
        int me = a[(left + right)/2];
        int le = a[right];

        //Rearrange them into the right order

        int temp;

        //First element

        if(me < fe && me <= le){
                temp=fe;
                fe=me;
                me=temp;
        }
        if(le < fe && le <= me){
                temp=fe;
                fe=le;
                le=temp;
        }

        //Second element

        if(le < me){
                temp=me;
                me=le;
                le=temp;
        }

        //Rewrite to array

        a[left]=fe;
        a[(left+right)/2]=me;
        a[right]=le;

        //Assert #1 - ensure all of the elements are in order

        assert(fe <= me && fe <= le && me <= le);

        //Setup for the loop:
        //If there are 3 or less  elements left, then just return the index of the pivot

        if(right - left <= 2) return (left+right)/2;

        //Move the pivot out of the way

        int pivot = a[(left+right)/2];
        temp = a[right-1];
        a[right-1]=pivot;
        a[(left+right)/2]=temp;	

        //Initial counters, we go from right-1, so j=1 to start
        //Assert #2 - Ensure that the pivot is moved out of the way

        assert(a[right-1]==pivot);
        int i=0; int j=1;

        //Actual loop:

        for(;;){
                //The first do-loop, incrementing the left side	
                do{
                        i++;
                }
                while(a[left+i] < a[right-1]);
                //The second do-loop, decrementing the right side
                do{
                        j++;
                }
                while(a[right-j] >= a[right-1]);
                //If the two indices have crossed each other, then we are done
                if((left+i) >= (right-j)){
                        temp=a[left+i];
                        a[left+i]=a[right-1];
                        a[right-1]=temp;
                        //Assert #3 - Make sure that the pivot is put back correctly
                        assert(a[left+i]==pivot);
                        return (left+i);
                }
                //Otherwise we need to swap the elements and reset the counters
                else{
                        //Assert #4 - Ensure that the scanners have not crossed.
                        assert(left+i < right-j);
                        temp=a[left+i];
                        a[left+i]=a[right-j];
                        a[right-j]=temp;
                        i=0;
                        j=1;
                }	 	
        }
}

void printArray(int a[], int n) {
        for(int i=0; i<n; i++) {
                printf("%d ", a[i]);
        }
        printf("\n");
}

//The main function, which will be used for testing at some point.
//This should be modified to accept varying input at some point

//#define SIZE 3000 

int main(){
        int *a;
        int SIZE = 0;
        scanf("%d", &SIZE);
        a = malloc(SIZE * sizeof(int));
        srand(time(NULL));
        int i = 0;
        for (; i < SIZE; i++) {
                a[i] = rand() % 1000;
        }

        quicksort(a,SIZE);
        print_array(a,SIZE);
        printf("%d", SIZE * sizeof(int));
        free(a);
        return 0;
}
